/**
 * 不同路径
 * 示例
 * 输入：m = 3, n = 2
 * 输出：3
 * 解释：
 * 从左上角开始，总共有 3 条路径可以到达右下角。
 * 1. 向右 -> 向下 -> 向下
 * 2. 向下 -> 向下 -> 向右
 * 3. 向下 -> 向右 -> 向下
 *
 * @param {number} row 行
 * @param {number} col 列
 * @see https://leetcode-cn.com/problems/unique-paths/
 * @summary https://zhuanlan.zhihu.com/p/91582909
 */
function uniquePaths(row: number, col: number) {
  /**
   * 生成网格
   * 注意，这个网格相当于一个二维数组，数组是从下标为 0 开始算起的
   * 所以 右下角的位置是 (row-1, col- 1)，所以 dp[row-1] [col-1] 就是我们要找的答案
   */
  const dp: number[][] = Array.from({length: row}, () => Array.from({length: col}))

  /**
   * 初始化 每行第一列值为 1
   */
  for (let i = 0; i < row; i++) dp[i][0] = 1

  /**
   * 初始化 每列第一行值为 1
   */
  for (let i = 0; i < col; i++) dp[0][i] = 1

  /**
   * 机器人要怎么样才能到达 (i, j) 这个位置？由于机器人可以向下走或者向右走，所以有两种方式到达
   * 一种是从 (i-1, j) 这个位置走一步到达
   * 一种是从(i, j-1) 这个位置走一步到达
   * 因为是计算所有可能的步骤，所以是把所有可能走的路径都加起来，所以关系式是 dp[i][j] = dp[i-1][j] + dp[i][j-1]
   */
  for (let i = 1; i < row; i++) {
    for (let j = 1; j < col; j++) {
      dp[i][j] = dp[i-1][j] + dp[i][j-1]
    }
  }

  return dp[row-1][col-1]
}

console.log(uniquePaths(7,3))
